#![feature(dropck_eyepatch)]

use std::marker::PhantomData;
use std::mem;

struct Unique<T> {
    ptr: *const T,
    _marker: PhantomData<T>,
}


unsafe impl<T: Send> Send for Unique<T> {}

unsafe impl<T: Sync> Sync for Unique<T> {}


impl<T> Unique<T> {
    pub const fn new(ptr: *mut T) -> Self {
        Unique { ptr: ptr, _marker: PhantomData }
    }
    pub fn as_ptr(&self) -> *mut T {
        self.ptr as *mut T
    }
}


impl<T: Sized> Unique<T> {
    #[inline]
    pub const fn dangling() -> Self {
        Unique::new(mem::align_of::<T>() as *mut T)
    }
}



struct RawVec<T> {
    ptr: Unique<T>,
    cap: usize,
}

impl<T> RawVec<T> {
    fn new() -> RawVec<T> {
        let cap = if mem::size_of::<T>() == 0 { !0 } else { 0 };
        RawVec {
            ptr: Unique::dangling(),
            cap: cap,
        }
    }

    fn grow(&mut self) {
        let elem_size = mem::size_of::<T>();

        assert!(elem_size != 0, "capacity overflow");

        let (new_cap, new_layout) = if self.cap == 0 {
            (1, Layout::array::<T>(1).unwrap())
        } else {
            // This can't overflow since self.cap <= isize::MAX.
            let new_cap = 2 * self.cap;

            // `Layout::array` checks that the number of bytes is <= usize::MAX,
            // but this is redundant since old_layout.size() <= isize::MAX,
            // so the `unwrap` should never fail.
            let new_layout = Layout::array::<T>(new_cap).unwrap();
            (new_cap, new_layout)
        };

        // Ensure that the new allocation doesn't exceed `isize::MAX` bytes.
        assert!(new_layout.size() <= isize::MAX as usize, "Allocation too large");

        let new_ptr = if self.cap == 0 {
            unsafe { alloc::alloc(new_layout) }
        } else {
            let old_layout = Layout::array::<T>(self.cap).unwrap();
            let old_ptr = self.ptr.as_ptr() as *mut u8;
            unsafe { alloc::realloc(old_ptr, old_layout, new_layout.size()) }
        };

        // If allocation fails, `new_ptr` will be null, in which case we abort.
        self.ptr = if new_ptr.is_null() {
            alloc::handle_alloc_error(new_layout);
        } else {
            Unique::new(new_ptr as *mut T)
        };
        self.cap = new_cap;
    }
}

unsafe impl<#[may_dangle] T> Drop for RawVec<T> {
    fn drop(&mut self) {
        if mem::size_of::<T>() == 0 || self.cap == 0 {
            return;
        }

        let layout = Layout::array::<T>(self.cap).unwrap();
        unsafe {
            alloc::dealloc(self.ptr.as_ptr() as _, layout);
        }
    }
}


pub struct MyVec<T> {
    buf: RawVec<T>,
    len: usize,
}


impl<T> MyVec<T> {
    pub fn new() -> Self {
        MyVec { buf: RawVec::new(), len: 0 }
    }
}


use std::alloc::{self, Layout, dealloc};

impl<T> MyVec<T> {}

use std::ptr;
use std::ops::{Deref, DerefMut};
use std::ptr::copy;
use std::option::Option::Some;
use std::iter::{StepBy, Chain, Zip, Intersperse, IntersperseWith, Map, Filter, FilterMap, Enumerate, Peekable, SkipWhile, TakeWhile, Skip, Take, Scan, FlatMap, Flatten, Fuse, Inspect, FromIterator, Rev, Copied, Cloned, Cycle, Sum, Product};
use std::convert::Infallible;
use std::cmp::Ordering;

impl<T> MyVec<T> {
    pub fn push(&mut self, elem: T) {
        if self.len == self.buf.cap {
            self.buf.grow();
        }
        unsafe {
            self.buf.ptr.as_ptr().offset(self.len as isize).write(elem);
        }
        self.len += 1;
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.len == 0 {
            return None;
        }
        self.len -= 1;
        unsafe {
            Some(self.buf.ptr.as_ptr().offset(self.len as isize).read())
        }
    }

    pub fn insert(&mut self, index: usize, elem: T) {
        assert!(index <= self.len, "index out of bounds");
        if self.len == self.buf.cap {
            self.buf.grow();
        }
        unsafe {
            self.buf.ptr.as_ptr().offset(index as isize).
                copy_to(
                    self.buf.ptr.as_ptr().offset((index + 1) as isize),
                    self.len - index,
                );
            self.buf.ptr.as_ptr().offset(index as isize).write(elem);
        }
        self.len += 1;
    }

    pub fn remove(&mut self, index: usize) {
        assert!(index < self.len, "index out of bounds");
        unsafe {
            self.buf.ptr.as_ptr().offset(index as isize).read();
        }
        self.len -= 1;
        unsafe {
            self.buf.ptr.as_ptr().offset((index + 1) as isize).copy_to(self.buf.ptr.as_ptr().offset(index as isize), self.len - index);
        }
    }

    pub fn get(&self, index: usize) -> &T {
        assert!(index < self.len, "index out of bounds");
        unsafe {
            &*self.buf.ptr.as_ptr().offset(index as isize)
        }
    }
}


unsafe impl<#[may_dangle]T> Drop for MyVec<T> {
    fn drop(&mut self) {
        println!("drop[MyVec]");
        while let Some(_) = self.pop() {}
    }
}

pub struct IntoIter<T> {
    buf: RawVec<T>,
    start: *const T,
    end: *const T,
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        if self.start == self.end {
            return None;
        }
        unsafe {
            let data = Some((self.start as *mut T).read());
            self.start = self.start.offset(1);
            data
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let len = (self.end as usize - self.start as usize) / mem::size_of::<T>();
        (len, Some(len))
    }
}

impl<T> DoubleEndedIterator for IntoIter<T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.start == self.end {
            return None;
        }
        unsafe {
            self.end = self.end.offset(-1);
            Some((self.end as *mut T).read())
        }
    }
}

unsafe impl<#[may_dangle]T> Drop for IntoIter<T> {
    fn drop(&mut self) {
        println!("drop[IntoIter]");
        for _ in self.into_iter() {};
    }
}

use std::mem::ManuallyDrop;


impl<T> IntoIterator for MyVec<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;

    fn into_iter(self) -> IntoIter<T> {
        // 因为Vec是Drop，不能销毁它
        let len = self.len;
        let buf = unsafe {
            ptr::read(&self.buf)
        };
        mem::forget(self);
        // 确保Vec不会被drop，因为那样会释放内存空间
        unsafe {
            IntoIter {
                start: buf.ptr.ptr,
                end: buf.ptr.ptr.offset(len as isize),
                buf: buf,
            }
        }
    }
}




